package binaryTree.bst;
/**
 * @Title: BinarySearchTree_v1.java 
 * @Package binaryTree.bst 
 * @Description: 二分搜索树，递归插入元素
 * @author CandyWall   
 * @date 2021年1月5日 上午9:04:45 
 * @version V1.0
 */
public class CandyBinarySearchTree_v1<E extends Comparable<E>> {
    private class Node {
        public E e;
        public Node left, right;
        
        public Node(E e) {
            this.e = e;
            left = right = null;
        }
    }
    
    private Node root;
    private int size;
    
    public CandyBinarySearchTree_v1() {
        root = null;
        size = 0;
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public void add(E e) {
        //根节点为空的时候需要特殊考虑
        if(root == null) {
            root = new Node(e);
            size++;
        } else {
            add(root, e);
        }
    }
    
    // 向以node为根的二分搜索树中插入元素e，递归算法
    public void add(Node node, E e) {
        if (e.equals(node.e)) {
            return;
        } else if (e.compareTo(node.e) < 0 && node.left == null) {
            node.left = new Node(e);
            size++;
            return;
        } else if (e.compareTo(node.e) > 0 && node.right == null) {
            node.right = new Node(e);
            size++;
            return;
        } 
        
        if (e.compareTo(node.e) < 0) {
            add(node.left, e);
        } 
        else {// if(e.compareTo(node.e) > 0) {
            add(node.right, e);
        }
    }
}
